package leetcode.d_1_99;

// https://leetcode.cn/problems/trapping-rain-water/
// 接雨水
public class P42 {
    public int trap(int[] height) {
        int n = height.length;
        // 左边的柱子的最小值
        int[] maxLeft = new int[n];
        int maxL = height[0];
        for (int i=1; i<n; i++) {
            if (height[i-1] > maxL) {
                maxL = height[i-1];
            }
            maxLeft[i] = maxL;
        }
        // 右边柱子的最小值
        int[] maxRight = new int[n];
        int maxR = height[n-1];
        for (int i=n-2; i>=0; i--) {
            if (height[i+1] > maxR) {
                maxR = height[i+1];
            }
            maxRight[i] = maxR;
        }

        int sum = 0;
        for (int i=0; i<n; i++) {
            int maxHeight = Math.min(maxLeft[i], maxRight[i]);
            if (maxHeight > height[i]) {
                int value = maxHeight - height[i];
                sum += value;
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        P42 test = new P42();
        System.out.println(test.trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1})); // 6
    }
}
